import java.util.Stack;

/**
 * 224. 基本计算器
 *
 * 实现一个基本的计算器来计算一个简单的字符串表达式的值。
 *
 * 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。
 *
 * 示例 1:
 * 输入: "1 + 1"
 * 输出: 2
 *
 * 示例 2:
 * 输入: " 2-1 + 2 "
 * 输出: 3
 *
 * 示例 3:
 * 输入: "(1+(4+5+2)-3)+(6+8)"
 * 输出: 23
 *
 * 说明：
 *     你可以假设所给定的表达式都是有效的。
 *     请不要使用内置的库函数 eval。
 */
public class Solution_224 {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        //当前正在操作的数
        int operand = 0;
        //保存最近最新的结果
        int result = 0;
        //符号
        int sign = 1;
        //数组长度
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                //如果是数字， 123 --> 120 + 3 --> 100 + 20 + 3
                operand = operand*10 + (int)(c - '0');
            } else if (c == '+'){
                result += operand*sign;
                sign = 1;
                operand = 0;
            } else if (c == '-'){
                result += operand*sign;
                sign = -1;
                operand = 0;
            } else if (c == '('){
                //将**当前的**的结果保存
                stack.push(result);
                stack.push(sign);

                //初始化
                result = 0;
                sign = 1;
            } else if (c == ')'){
                //计算本次结果并且和**上一次**的结果进行计算
                result += operand*sign;
                //和上一次结果进行计算
                result *= stack.pop();
                result += stack.pop();
                //初始化
                operand = 0;
            }
        }
        //返回最终结果，当遍历完数组的时候，result还不是最终的结果，因此，还要进行最后一次计算
        return result + (sign * operand);
    }
}
